1. Field of the invention
The present invention relates to the field of telecommunications and more particularly to a routing method for a router in a telecommunications network.
2. Description of the Related Art
In the last few years, telecommunications networks have considerably developed, in particular with the rise of the Internet network and the growth of companies' private networks (also known as “intranets”). Thus, any user can communicate with any other operator of the network—correspondent or server—, in order to exchange information or to access resources available on the network. Regarding the Internet network's architecture, the basic element thereof is the router that is in charge of the transit of information packets for routing same to their respective recipients.
FIG. 1 illustrates a typical network topography diagram in which three networks or intranets—respectively 1, 2 and 3—are connected to a set of routers 10, 20, 30, 40 and 50 through links. More particularly, router 10 has a first port connected to a link 11 enabling communication with intranet 1, a second port connected to a link 12 for accessing router 20 and, for instance, a third port enabling communication with router 30 via a link 13.
In the Ipv4 version of the Internet network, the destination address of each packet is four bytes (i.e., 32 bits) long and said address is used within each router in order to enable transit of the IP packet that is input through one of the ports of said router—for example port 11 of router 10 for an information packet coming from intranet 1—towards one of the other ports of said router, in order to route it to its recipient, for example a particular correspondent of intranet 2. Practically, the routing of a packet towards the router's correct port is ensured by means of a routing table locally implemented within the router, and allowing, whenever a given packet comes in with an IP address characterizing a recipient, to decode said address, in order to determine the particular port towards which the packet must be redirected among the router's set of available ports. When the table does not contain any specific information related to the routing of a given packet, said packet is then automatically directed towards a default port that is typically arranged for routing of said packet towards a router that will have more information allowing to correctly route said packet.
In modern networks, it is current for routers' routing tables to contain several tens of thousands of inputs that network administrators try to maintain and update in order to ensure an optimal operation of networks. In the case, for example, of a router having approximately 60,000 inputs, with ten bytes (4 bytes for the address, 4 bytes for the network mask and at least 1 byte for the port) associated with each input, the corresponding routing table will necessarily have approximately 600 Kbytes. The problem is that if this table is stored with no particular precaution, the whole table must be entirely looked-up for each incoming packet. Even with the most sophisticated machines—allowing to read 64 bits in a single operation—at least two reading operations are required to read an input. For 60,000 inputs, an average of several thousands of reading operations for a given packet are thus necessary, going up to 120,000 operations in the worst case, which considerably increases packet transit time in the router.
A known technique, described in <<IP address lookup made fast and simple>> by Pierluigi Crescenzi, Leandro Dardini and Roberto Grossi, Università di Pisa, Dipartimento di Informatica, Technical Report TR-99-01, makes it possible to reduce the reading of the table to three operations, however at the cost of a considerable increase in size of this table, which can then reach several megabytes. Such a table—realized with RAM in order to minimize access times to information stored therein—is expensive to implement. Moreover, such a large sized RAM is out of proportion with the possibilities of the semiconductor manufacturing technology, which definitively precludes its integration into a semiconductor circuit. It should further be observed that, in the known system, complete overhauling of the table is required when table updating is to be made, which obviously does not facilitate maintenance of the system.
Another known technique is described in U.S. Pat. No. 6,266,706. It makes it possible to reduce the size of the table to a few hundreds kilobytes and to limit the number of reading operations to six. However, maintenance of this table is particularly delicate owing to the fact that it is necessary to completely rebuild same whenever it is updated.
One is thus confronted with the following dilemma: either accepting to deal with a large routing table—which, currently, cannot be integrated in a semiconductor circuit—or considerably lengthening packet routing time.